class LRUCache {
    private class Node{
        int key;
        int value;
        Node pre;
        Node next;
    };

    private HashMap<Integer,Node> map;
    private Node head;
    private Node tail;
    private int capacity;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer,Node>();
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;

    }
    
    public int get(int key) {
        // 从map中取出节点
        if(!map.containsKey(key)) return -1;
        Node node = map.get(key);
        // 将这个节点从链表中删除
        this.removeNodeInList(node);
        // 将这个节点插入到链表头部
        this.insertToListHead(node.key,node.value);
        return node.value;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            // 如果内容已在链表中
            // 将内容在链表中删除
            Node node = map.get(key);
            this.removeNodeInList(node);
            // 将这个节点插入到链表头部
            this.insertToListHead(key,value);
        }else{
            // 如果内容不在链表中
            this.insertToListHead(key,value);
        }
        if(map.size() > capacity){
            this.removeNodeInList(tail.pre);
        }
    }

    private void removeNodeInList(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.remove(node.key);
    }

    private Node insertToListHead(int key, int value){
        Node node = new Node();
        node.key = key;
        node.value = value;
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        this.map.put(key,node);
        return node;
    }
}
